/// @tags: Exclusion Stirling
#include <cstdio>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef long long LL;

int const N = 3e3 + 5;

int mod;
int S[N][N], C[N][N];

inline int add(int a, int b) {
  a += b;
  return a >= mod ? a - mod : a;
}

inline LL qpow(LL base, int exp, int P = mod) {
  LL ans = 1;
  while (exp) {
    if (exp & 1) ans = ans * base % P;
    base = base * base % P, exp >>= 1;
  }
  return ans;
}

inline void prework(int n) {
  C[0][0] = S[0][0] = 1;
  for (int i = 1; i <= n + 1; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      S[i][j] = add(S[i - 1][j - 1], (LL)S[i - 1][j] * j % mod);
      C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
    }
  }
}

inline int main() {
  int n;
  cin >> n >> mod;
  prework(n);
  int ans = 0;
  for (int i = 0; i <= n; ++i) {
    LL exp = qpow(2, n - i), mul = i & 1 ? mod - 1 : 1, res = 0;
    mul = mul * C[n][i] % mod * qpow(2, qpow(2, n - i, mod - 1)) % mod;
    LL fac = 1;
    for (int j = 0; j <= i; ++j)
      res = add(res, S[i + 1][j + 1] * fac % mod), fac = fac * exp % mod;
    ans = add(ans, res * mul % mod);
  }
  cout << ans;
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("AT4119 [ARC096C] Everything on It.in", "r", stdin);
  freopen("AT4119 [ARC096C] Everything on It.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
